package com.buddy.summary.code.algorithm;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {

    private static class TreeNode{
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data){
            this.data = data;
        }
    }

    private static TreeNode createBinaryTreeNode(LinkedList<Integer> inputList){
        TreeNode treeNode = null;
        if (inputList == null || inputList.isEmpty()){
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null){
            treeNode = new TreeNode(data);
            treeNode.left = createBinaryTreeNode(inputList);
            treeNode.right = createBinaryTreeNode(inputList);
        }
        return treeNode;
    }


    //前序遍历:root left right
    private static void preOrderTraversal(TreeNode treeNode){
        if (treeNode == null){
            return;
        }
        System.out.println(treeNode.data);
        preOrderTraversal(treeNode.left);
        preOrderTraversal(treeNode.right);
    }

    //中序遍历: left root right
    private static void inOrderTraversal(TreeNode treeNode){
        if (treeNode == null){
            return;
        }
        inOrderTraversal(treeNode.left);
        System.out.println(treeNode.data);
        inOrderTraversal(treeNode.right);
    }

    //后序遍历: left right root
    private static void postOrderTraversal(TreeNode treeNode){
        if (treeNode == null){
            return;
        }
        postOrderTraversal(treeNode.left);
        postOrderTraversal(treeNode.right);
        System.out.println(treeNode.data);
    }

    //二叉树非递归前序遍历 root left right
    private static void preOrderTraversalWithStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()){
            //迭代访问left,并入栈
            while (treeNode != null){
                System.out.println(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.left;
            }
            //如果没有left则弹出栈顶节点,访问right
            if (!stack.isEmpty()){
                treeNode = stack.pop();
                treeNode = treeNode.right;
            }
        }

    }

    //二叉树非递归中序遍历 left root right
    private static void inOrderTraversalWithStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()){
            //迭代left,并入栈
            while (treeNode != null){
                stack.push(treeNode);
                treeNode = treeNode.left;
            }
            //如果没有left则弹出栈顶,访问right
            if (!stack.isEmpty()){
                treeNode = stack.pop();
                System.out.println(treeNode.data);
                treeNode = treeNode.right;
            }
        }
    }
    //二叉树非递归后序遍历 left right root
    private static void postOrderTraversalWithStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> tempStack = new Stack<>();
        TreeNode treeNode = root;
        while(treeNode != null || !stack.isEmpty()){
            while (treeNode != null){
                stack.push(treeNode);
                tempStack.push(treeNode);
                treeNode = treeNode.right;
            }
            if (!stack.isEmpty()){
                treeNode = stack.pop();
                treeNode = treeNode.left;
            }
        }
        while (!tempStack.isEmpty()){
            TreeNode node = tempStack.pop();
            System.out.println(node.data);
        }
    }

    private static void levelOrderTraversal(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode treeNode = queue.poll();
            System.out.println(treeNode.data);
            if (treeNode.left != null){
                queue.offer(treeNode.left);
            }
            if (treeNode.right != null){
                queue.offer(treeNode.right);
            }
        }
    }

    public static void main(String[] args) {
        LinkedList<Integer> inputList = new LinkedList<>(
                Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4})
        );
        TreeNode treeNode = createBinaryTreeNode(inputList);
        System.out.println("前序遍历:");
        preOrderTraversal(treeNode);
        System.out.println("中序遍历:");
        inOrderTraversal(treeNode);
        System.out.println("后序遍历:");
        postOrderTraversal(treeNode);
        System.out.println("二叉树非递归前序遍历:");
        preOrderTraversalWithStack(treeNode);
        System.out.println("二叉树非递归中序遍历:");
        inOrderTraversalWithStack(treeNode);
        System.out.println("二叉树非递归后序遍历:");
        postOrderTraversalWithStack(treeNode);
        System.out.println("二叉树广度优先遍历:");
        levelOrderTraversal(treeNode);
    }

}
